#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    vector<int> nextArray(string needle)
    {
        int n = needle.size();
        vector<int> next(n, -1);
        if (n == 1)
        {
            return next;
        }
        next[0] = -1;
        next[1] = 0;
        int pre = 0;
        int i = 2;
        while (i < n)
        {
            if (needle[i - 1] == needle[pre])
            {
                next[i++] = ++pre;
            }
            else if (pre > 0)
            {
                pre = next[pre];
            }
            else
            {
                next[i++] = 0;
            }
        }
        return next;
    }
    int KMP(string haystack, string needle)
    {
        vector<int> next = nextArray(needle);
        int x = 0;
        int y = 0;
        while (x < haystack.size() && y < needle.size())
        {
            if (haystack[x] == needle[y])
            {
                x++;
                y++;
            }
            else if (y == 0)
            {
                x++;
            }
            else
            {
                y = next[y];
            }
        }
        return y == needle.size() ? x - needle.size() : -1;
    }
    int strStr(string haystack, string needle)
    {
        return KMP(haystack, needle);
    }
};